Extensible Markup Language (“XML”) has evolved into a standard for data representation and information exchange over the internet. XML data models generally model XML as a tree of element nodes (“elements”). Elements in an XML tree may be connected via parent-child edges or ancestor-descendent edges. As XML trees grow in size, the challenge of efficiently querying XML trees increases both in terms of efficiency and memory consumption.
A query expression specifying a pattern to be matched from the XML tree may be viewed as a tree-modeled substructure. Such tree-modeled substructures are typically referred to as XML twigs as the pattern they represent indicates a selection predicate over not only the data represented by the elements themselves, but also the structural relation of elements in the tree (i.e. the parent-child edges or ancestor-descendent edges of the tree). “Holistic” twig query processing techniques have been developed to minimize the intermediate root-to-leaf path matches that will not generate final XML twig results. Some “holistic” XML twig pattern matching schemes have been even suggested that can “holistically” match an XML twig including a specific Boolean predicate. In an attempt to reduce costly post-processing for redundant data and/or grouping of the matching results from intermediate path matches, “Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML documents” by Chen et al., the contents of which are incorporated herein by reference, suggested a hierarchical stack encoding scheme to compactly represent twig results and a bottom-up algorithm for processing twig queries based on the encoding scheme.
However, current “holistic” schemes deal only with XML twig queries limited to having a single primary Boolean predicate. In other words, while one solution has been suggested that may match a query XML twig that includes an AND Boolean predicate and another solution has been suggested that may match a query XML twig that includes an OR Boolean predicate, no single solution exists that provides the flexibility to handle arbitrary Boolean predicates. Additionally, current XML twig query processing schemes continue to use large amounts of memory to store intermediate results.
While systems, methods, and computer-readable media are described herein by way of examples and embodiments, those skilled in the art recognize that bottom-up query processing schemes for XML twigs with arbitrary Boolean predicates are not limited to the embodiments or drawings described. Rather, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the appended claims. Any headings used herein are for organizational purposes only and are not meant to limit the scope of the description or the claims. As used herein, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include”, “including”, and “includes” mean including, but not limited to.